Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prova scritta del 29 Maggio 2003

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Siano A, B e C tre insiemi assegnati. Usando esclusivamente i simboli di unione ∪, intersezione ∩, differenza insiemistica \, insieme vuoto ∅, inclusione ⊆, uguaglianza =, non uguaglianza ≠, e le parentesi, si formalizzino i seguenti enunciati: (Attenzione: non si può usare il simbolo ∈ di appartenenza).

1. Ogni elemento di C appartiene a B o ad A.

2. Non vi sono elementi di B che appartengono ad A ma non a C.

Esercizio 2. Nel linguaggio dei numeri naturali contenente i simboli di somma +, prodotto ·, ordine <, predicato di divisibilità |, e il predicato P (x) per “x è un numero primo”, si formalizzi il seguente enunciato:

1. Esiste un divisore primo di 121 maggiore di 10.

2. Usando le usuali notazioni insiemistiche (oltre ai simboli menzionati sopra), si scriva una espressione che denoti l’insieme di tutti i numeri n ∈ ℕ che hanno un divisore primo maggiore di 10.

Esercizio 3. Le estrazioni del lotto consistono nell’estrazione di 5 numeri distinti dall’insieme dei 90 numeri interi da 1 a 90 (non conta l’ordine con cui sono estratti).

• Quante sono tutte le possibili estrazioni?

Marco gioca i numeri 15, 30, 45, 60 e 75.

• Quante sono le possibili estrazioni che non contengono alcuno dei numeri da lui giocati?

• Quante sono le estrazioni che contengono esattamente due dei numeri da lui giocati?

Esercizio 4.

1. Sia g la funzione dall’insieme {0, 1, 2, 3, 4, 5, 6, 7} in se stesso che manda x in 4x mod 8 (cioè g(x) è il resto della divisione di 4x per 8). Determinare se g è iniettiva, surgettiva, biunivoca.

2. Sia h la funzione dall’insieme {0, 1, 2, 3, 4, 5, 6, 7} in se stesso che manda x in 3x mod 8. Determinare se h è iniettiva, surgettiva, biunivoca.

3. Sia f la funzione dall’insieme {0, 1, 2, 3, 4, 5, 6} in se stesso che manda x in 2x + 5 modulo 7. Dimostrare che f è invertibile. Dimostrare inoltre che esistono a, b ∈ {0, 1, 2, 3, 4, 5, 6} tali che f^{−1}(x) = ax + b mod 7. Trovare tali numeri a e b.

Esercizio 5. Si dimostri per induzione su n ∈ ℕ che n^{n} ≥ n!.